package com.practice.dp;

public class StringShuffle {
	public boolean isShuffle(String X, String Y, String Z) {
		int N = X.length();
		int M = Y.length();
		if (Z.length() != N + M) return false;
		
		boolean[][] b = new boolean[N+1][M+1];
		b[0][0] = true;
		
		for (int L=1; L<=N+M; L++) {
			for (int i=0; i<=L && i<=N; i++) {
				int j = L - i;
				if (j > M) continue;
				
				if (i>0) b[i][j] |= b[i-1][j] && X.charAt(i-1) == Z.charAt(i+j-1);
				if (j>0) b[i][j] |= b[i][j-1] && Y.charAt(j-1) == Z.charAt(i+j-1);
			}
		}
		
		return b[N][M];
	}
}
